package LeetCode.exercise;

public class LC494 {
    int count = 0;
    int tmp = 0;

    public int findTargetSumWays(int[] nums, int target) {
        bfs(nums, target, 0);
        return count;
    }

    public void bfs(int[] nums, int target, int cur) {
        if (cur >= nums.length){
            if(tmp == target) {
                count++;
            }
            return;
        }
        tmp += nums[cur];
        bfs(nums, target, cur + 1);
        tmp -= nums[cur];

        tmp -= nums[cur];
        bfs(nums, target, cur + 1);
        tmp += nums[cur];
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        LC494 lc494 = new LC494();
        System.out.println(lc494.findTargetSumWays(nums, 3));
    }
}
